package sim.util;

import java.util.*;

/**
 * Implements a binary heap. Note that all "matching" is based on the compareTo
 * method.
 * 
 * @author Mark Allen Weiss
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<T extends Comparable> implements Iterable<T> {
	/**
	 * Construct the binary heap.
	 */
	public BinaryHeap() {
		currentSize = 0;
	}

	/**
	 * Insert into the priority queue. Duplicates are allowed.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void insert(T x) {
		int hole = ++currentSize;
		try {
			array[hole] = x;
		} catch (Exception e) {
			createOrdoubleArray(x) ;
		}			
		array[0] = x;
		array[hole] = x;
		
		for (; x.compareTo(array[hole / 2]) < 0; hole /= 2)
			array[hole] = array[hole / 2];
		array[hole] = x;
	}

	/**
	 * Find the smallest item in the priority queue.
	 * 
	 * @return the smallest item.
	 * @throws UnderflowException
	 *             if empty.
	 */
	public T minimum() {
		if (isEmpty()) throw new RuntimeException("Empty binary heap");
		return (T) array[1];
	}

	/**
	 * Update the smallest item from the priority queue.
	 * 
	 * @throws UnderflowException if empty.
	 */
	public void updateMin() {
		percolateDown(1);
	}

	/**
	 * Remove the smallest item from the priority queue.
	 * 
	 * @return the smallest item.
	 * @throws UnderflowException
	 *             if empty.
	 */
	public T deleteMin() {
		T minItem = minimum();
		array[1] = array[currentSize--];
		percolateDown(1);
		return minItem;
	}

	/**
	 * Test if the priority queue is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return currentSize == 0;
	}

	/**
	 * Returns size.
	 * 
	 * @return current size.
	 */
	public int size() {
		return currentSize;
	}

	/**
	 * Make the priority queue logically empty.
	 */
	public void makeEmpty() {
		currentSize = 0;
	}

	private static final int DEFAULT_CAPACITY = 1024;

	private int currentSize; // Number of elements in heap
	@SuppressWarnings("unchecked")
	private Comparable[] array; // The heap array

	/**
	 * Internal method to percolate down in the heap.
	 * 
	 * @param hole
	 *            the index at which the percolate begins.
	 */
	@SuppressWarnings("unchecked")
	private void percolateDown(int hole) {
		int child;
		Comparable tmp = array[hole];

		for (; hole * 2 <= currentSize; hole = child) {
			child = hole * 2;
			if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) child++;
			if (array[child].compareTo(tmp) < 0)
				array[hole] = array[child];
			else
				break;
		}
		array[hole] = tmp;
	}

	@SuppressWarnings("unchecked")
	private void createOrdoubleArray(T proto) {
		int size = array == null ? DEFAULT_CAPACITY : 2 * array.length;
		Comparable[] newArray = new Comparable[ size ];
		if (array != null) 
			System.arraycopy(array, 0, newArray, 0, array.length ) ;
		
		array = newArray;
	}

	public String toString() {
		if( array == null) return "[]" ;
		TreeSet<Comparable> x = new TreeSet<Comparable>() ;
		for( int i = 0 ; i <= currentSize ; i++ )
			x.add( array[i]) ;
		
		return x.toString() ;
		
	}

	public Iterator<T> iterator() {
		return new HeapIterator() ;
	}
	
	private class HeapIterator implements Iterator<T> {
		int i = 0 ;
		public boolean hasNext() {
			return i <= currentSize ;
		}

		public T next() {
			return (T) array[i++] ;
		}

		public void remove() {}		
	}
}
